/*
    二维前缀和、二维差分、离散化技巧

    前置知识 : 讲解047-关于一维差分的内容

    二维前缀和的原理、代码实现、相关题目

    二维差分的原理、代码实现、相关题目

    离散化技巧，用具体题目来说明

    注意:
    支持实时单点修改 + 实时查询的结构是二维树状数组，会在【扩展】课程里讲述

    ================================================
    
    目的是预处理出一个结构，以后每次查询二维数组任何范围上的累加和都是O(1)的操作
    1 根据原始状况，生成二维前缀和数组sum，
    sum[i][j]: 代表左上角(0,0)到右下角(i,j)这个范围的累加和
    sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
    2 查询左上角(a,b)到右下角(c,d)这个范围的累加和
    sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
    3 实际过程中往往补第0行、第0列来减少很多条件判断。
    当然也可以不补。根据个人习惯决定。

    ================================================

    在二维数组中，如果经历如下的过程
    1 批量的做如下的操作，每个操作都有独立的a、b、c、d、v
    void add(a, b, c, d, v) : 左上角(a,b)到右下角(c,d)范围上，每个数字+v，怎么快速处理？
    2 操作做完后，如何正确得到二维数组中每个位置的值？

    这就是二维差分的主要工作，add时候快速处理，最后build得到每个位置的值，修改操作必须集中在一起，不能边修改边查询。
    1）add方法实现，比较巧妙！
    2）build方法实现，和处理前缀和类似
    3）真实数据用一圈0包裹起来，可以减少很多边界讨论

    void build() 
    {
		for (int i = 1; i <= n; i++) 
        {
			for (int j = 1; j <= n; j++) 
            {
				diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
			}
		}
	}

    void add(int a, int b, int c, int d, int v) 
    {
		diff[a][b] += v;
		diff[c + 1][b] -= v;
		diff[a][d + 1] -= v;
		diff[c + 1][d + 1] += v;
	}

    ================================================

    题目1
    二维前缀和模版
    https://leetcode.cn/problems/range-sum-query-2d-immutable/

    题目2
    边框为1的最大正方形
    给你一个由若干 0 和 1 组成的二维网格 grid
    请你找出边界全部由 1 组成的最大 正方形 子网格
    并返回该子网格中的元素数量。如果不存在，则返回 0。
    测试链接 : https://leetcode.cn/problems/largest-1-bordered-square/


    ================================================

    题目3
    二维差分模版
    https://www.nowcoder.com/practice/50e1a93989df42efb0b1dec386fb4ccc
    https://www.luogu.com.cn/problem/P3397


    题目4
    用邮票贴满网格图
    给你一个 m * n 的二进制矩阵 grid
    每个格子要么为 0 （空）要么为 1 （被占据）
    给你邮票的尺寸为 stampHeight * stampWidth
    我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ：
    覆盖所有空格子，不覆盖任何被占据的格子
    可以放入任意数目的邮票，邮票可以相互有重叠部分
    邮票不允许旋转，邮票必须完全在矩阵内
    如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false
    测试链接 : https://leetcode.cn/problems/stamping-the-grid/

    ================================================

    题目5
    重要！包含离散化技巧！
    最强祝福力场
    小扣在探索丛林的过程中，无意间发现了传说中"落寞的黄金之都"
    而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场
    经过不断的勘测记录，小扣将所有力场的分布都记录了下来
    forceField[i] = [x,y,side] 
    表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。
    若任意一点的 力场强度 等于覆盖该点的力场数量
    请求出在这片地带中 力场强度 最强处的 力场强度
    注意：力场范围的边缘同样被力场覆盖。
    测试链接 : https://leetcode.cn/problems/xepqZ5/

*/